package SortTable;

//堆排序 10.4.3    P282
public class HeapSort {
    public static void HeapAdjust(int[] arr,int s,int m){
        int rc=arr[s];
        for (int j=s*2;j<=m;j*=2){
            if (j<=m&&j+1<=m){
                if (arr[j]<arr[j+1]){
                    j++;
                }
            }
            if (rc>=arr[j]){
                break;
            }
           arr[s]=arr[j];
            s=j;//！！！！！
        }
        arr[s]=rc;
    }
    public static void HeapSort(int[] arr){
        //建造大顶堆
        for (int i=(arr.length-1)/2;i>0;i--){
            HeapAdjust(arr,i,arr.length-1);
        }

        for (int i=arr.length-1;i>1;i--){
            int temp=arr[1];
            arr[1]=arr[i];
            arr[i]=temp;
            //将余下的序列重新调整为大顶堆
            HeapAdjust(arr,1,i-1);
        }
    }

    public static void main(String[] args) {
         int[] arr={-1,6,7,8,3,4,5,2,8,9,40};
         HeapSort(arr);
        for (int i = 1; i <=arr.length-1 ; i++) {
            System.out.println(arr[i]);
        }
    }
}
